package stackqueue;

import java.util.ArrayDeque;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/9 1:36
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 */
public class MaxSlidingWindow {


    /**
     * 单调队列：队列里的元素一定是要排序的，而且要最大值（最小值）放在出队口
     * 对于窗口里的元素{2, 3, 5, 1 ,4}，单调队列里只维护{5, 4} 就够了，保持单调队列里单调递减，此
     * 时队列出口元素就是窗口里最大元素。    4为了下一个窗口准备，以防4是下个窗口的最大数
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        int count = 0, n = nums.length;
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            //nums[i]入队前，考虑某些元素出队：当前元素大于队中的元素
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            //当窗口准备滑动时，出队一个元素，队头元素与当前最大的元素相等(此算法用索引代替)时，出队
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            deque.offer(i);
            if (i >= k - 1) {
                result[count++] = nums[deque.peek()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3,1,2,0,5};
        int k = 3;
        int[] ints = maxSlidingWindow(nums, k);
        System.out.println();
    }
}
